package leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class FindRightInterval {

	public static void main(String[] args) {
		FindRightInterval object = new FindRightInterval();
		Interval[] intervals = {new Interval(3, 4), new Interval(2, 3), new Interval(1, 2)};
		int[] res = object.findRightInterval(intervals);
		for (int i = 0; i < res.length; i++) {
			System.out.print(res[i] + "  ");
		}
	}
	
	private static class Interval {
		int start;
		int end;

		Interval() {
			start = 0;
			end = 0;
		}

		Interval(int s, int e) {
			start = s;
			end = e;
		}
	}

	public int[] findRightInterval(Interval[] intervals) {
		Map<Interval, Integer> map = new HashMap<>();
		for (int i = 0; i < intervals.length; i++) {
			map.put(intervals[i], i);
		}
		Arrays.sort(intervals, new Comparator<Interval>() {
			@Override
			public int compare(Interval o1, Interval o2) {
				return o1.start - o2.start;
			}
		});
		Map<Interval, Integer> sortMap = new HashMap<>();
		for (int i = 0; i < intervals.length; i++) {
			sortMap.put(intervals[i], i);
		}
		int[] record = new int[intervals.length];
		for (int i = 0; i < intervals.length; i++) {
			int start = i;
			int end = intervals.length - 1;
			int middle = 0;
			while(start < end){
				middle = start + (end - start) / 2;
				if(intervals[middle].start >= intervals[i].end){
					//因为题目保证了start是不相同的
					end = middle;
				}else if(intervals[middle].start < intervals[i].end){
					start = middle + 1;
				}
			}
			record[i] = intervals[start].start < intervals[i].end ? -1 : map.get(intervals[start]);
		}
		int[] res = new int[intervals.length];
		for(int i = 0; i < intervals.length; i++){
			res[map.get(intervals[i])] = record[sortMap.get(intervals[i])];
		}
		//最后还要重新按照原始数组进行记录
		return res;
	}
}
